package leetcode.problems.P面试题0802迷路的机器人;

import java.util.*;

public class PathWithObstacles {
}

// DFS
class Solution {
    int m, n;
    int[][] vis;

    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        m = obstacleGrid.length;
        if (m < 1) return Collections.emptyList();
        n = obstacleGrid[0].length;
        vis = new int[m][n];
        return dfs(obstacleGrid, 0, 0);
    }

    // 判断是否可达：未出界、未被访问、未被障碍物占据
    private boolean accessible(int[][] obstacleGrid, int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n && obstacleGrid[i][j] == 0 && vis[i][j] == 0;
    }

    private LinkedList<List<Integer>> dfs(int[][] obstacleGrid, int i, int j) {
        LinkedList<List<Integer>> ans = new LinkedList<>();
        if (!accessible(obstacleGrid, i, j)) return ans;// 当前不可访问
        if (isTarget(i, j)) {// 到达目的
            ans.add(Arrays.asList(i, j));
            return ans;
        }
        vis[i][j] = 1;
        if (accessible(obstacleGrid, i + 1, j)) {// 下方可访问
            ans = dfs(obstacleGrid, i + 1, j);
        }
        if (ans.size() > 0) {
            ans.addFirst(Arrays.asList(i, j));
            return ans;
        }
        if (accessible(obstacleGrid, i, j + 1)) {// 右方可访问
            ans = dfs(obstacleGrid, i, j + 1);
        }
        if (ans.size() > 0) {
            ans.addFirst(Arrays.asList(i, j));
            return ans;
        }
        return ans;// 当前不可访问，返回空
    }

    private boolean isTarget(int i, int j) {
        return i == m - 1 && j == n - 1;
    }
}

// BFS + 记录上一个节点
class Solution1 {
    int[][] dirc = {{0, 1}, {1, 0}};
    boolean[][] vis;
    int m, n;

    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        m = obstacleGrid.length;
        if (m < 1) return new ArrayList<>();
        n = obstacleGrid[0].length;
        vis = new boolean[m][n];
        LinkedList<int[]> prev = new LinkedList<>();
        if (obstacleGrid[0][0] == 0) {
            prev.add(new int[]{0, 0});
            vis[0][0] = true;
            return bfs(prev, obstacleGrid);
        }
        return new LinkedList<>();
    }

    private LinkedList<List<Integer>> bfs(LinkedList<int[]> prev, int[][] map) {
        LinkedList<int[]> next = new LinkedList<>();
        for (int[] ord : prev) {
            int x = ord[0], y = ord[1];
            if (x == m - 1 && y == n - 1 && map[x][y] == 0) {// 找到终点
                LinkedList<List<Integer>> list = new LinkedList<>();
                list.add(Arrays.asList(x, y));
                return list;
            }
            for (int[] d : dirc) {// 向右或向下寻找临近节点
                int dx = x + d[0], dy = y + d[1];
                if (inRange(dx, dy) && !vis[dx][dy] && map[dx][dy] == 0) {
                    vis[dx][dy] = true;
                    next.addLast(new int[]{dx, dy});
                }
            }
        }
        if (next.size() < 1) return new LinkedList<>();// 没有下一步了，无法到达终点
        LinkedList<List<Integer>> ans = bfs(next, map);
        if (ans.size() < 1) return ans;// 后续的步骤也无法到达
        ans.addFirst(findPrev(prev, ans.get(0)));// 后续步骤能到达，则向前推理，不断寻找上一个临近节点
        return ans;
    }

    // 在candidateNodes中寻找next的上一个相邻节点
    private List<Integer> findPrev(List<int[]> candidateNodes, List<Integer> nextNode) {
        int x = nextNode.get(0), y = nextNode.get(1);
        for (int[] node : candidateNodes) {
            for (int[] d : dirc) {
                if (node[0] + d[0] == x && node[1] + d[1] == y) {// 那么此node是nextNode的相邻节点，将其返回
                    return new LinkedList<>(Arrays.asList(node[0], node[1]));
                }
            }
        }
        return null;
    }

    private boolean inRange(int i, int j) {
        return 0 <= i && i < m && 0 <= j && j < n;
    }
}